
Queues and Huffmans Tree
Khan S. Alam 13 https://E-next.in
Q 10.5 Explain how Huffman’s code helps in data compression.
The American Standard Code for Information Interchange (ASCII) is a fixed – length code;
that is, the character length does not vary.
Each ASCII character consists of 7 bits. Although the character E occurs more frequently
than the character Z, both are assigned the same number of bits. This consistency means
that every character uses the maximum number of bits.
Huffman code, on the other hand, makes character storage more efficient. In
Huffman code we assign shorter codes to characters that occur more frequently and longer
codes to those that occur less frequently.
For example, E and T, two characters that occur frequently in the English language, could
be assigned one bit each. A, O, R, and N, which also occur frequently but less frequently
than E and T, could be assigned two bits each. S, U, I, D, M, C, and G are the next most
frequent and could be assigned three bits each, and so forth.
In a given piece of text, only some of the characters require the maximum bit length. When
used in a network transmission, the overall length of the transmission is shorter if Huffman
- encoded characters are transmitted rather than fixed – length encoding; Huffman code is
therefore a popular data compression algorithm.
Huffman code is widely used for data compression; it reduces the number of bits sent or
stored.
Q 10.6 Solve the following university questions:
M2012-Q1(b)
Given the set of symbols and corresponding frequency table as below, explain the steps to
find the Huffman code.
Steps to find Huffman code is as follows:
1. Arrange the symbol in descending order of their frequency.
2. Now find the two nodes with the smallest frequency weights and join them to form a
third node. The weight of the third node is the combined weights of the original two
nodes. This new node is eligible to be combined with other nodes.
3. Repeat step 1 until all of the nodes on every level are combined into a single tree.
4. Assigning 1 to right child of a node and 0 to left child of a node.
5. Starting from root node till the leaf node, noting the generated Huffman code for
each symbol.